package com.unionfind_01;

/**
 * @Author: tgy
 * @Date: 1/11/21 3:35 PM
 *
 *          p1
 *          / \
 *        v1   v3
 *        /    \
 *       v2     v4
 *
 *      find: O(logN)
 *      union: O(1)
 */
public class UF_QuickUnion extends AbstractUnionFind{

    public UF_QuickUnion(int size) {
        super(size);
    }

    @Override
    public int find(int v) {

        while (parents[v] != v) {

            v = parents[v];
        }

        return v;
    }

    @Override
    public void union(int v1, int v2) {

        int p1 = find(v1);
        int p2 = find(v2);

        if (p1 == p2) {

            return;
        }

        justify(p1, p2);
    }

    protected void justify(int p1,int p2) {

        parents[p2] = p1;
    }

    public static void main(String[] args) {

        UF_QuickUnion quickUnion = new UF_QuickUnion(9);


        quickUnion.union(1,3);
        quickUnion.union(2,8);
        quickUnion.union(4,7);
        quickUnion.union(3,4);

        System.out.println(quickUnion.isSame(1, 4));

    }
}
